#include "../../head/myhead.h"

// 字符单链表结构体
typedef struct CLNode
{
    char data;
    struct CLNode *next;
} CLNode;

/**
 * *********************************************************************************************************************
 * *******************************************************顺序表********************************************************
 * *********************************************************************************************************************
 */

/**初始化顺序表*/
void initSqList(SqList &l)
{
    l.length = 0;
}

/**顺序表增删改查*/
// 增
int insertSqList(SqList &l, int target)
{
    if (l.length < MAXSIZE)
    {
        l.data[l.length] = target;
        l.length += 1;
        return 1;
    }
    return 0;
}
// targe为需要删除的元素的下标，下标从0开始
int deleteSqList(SqList &l, int target)
{
    if (l.length >= 0)
    {
        for (int i = target; i < l.length - 1; i++)
        {
            l.data[i] = l.data[i + 1];
            l.length -= 1;
        }
        return 1;
    }
    return 0;
}
// 改，将下标为x的元素修改为target
int changeSqList(SqList &l, int x, int target)
{
    if (l.length > 0)
    {
        l.data[x] = target;
        return 1;
    }
    return 0;
}
// 若找到返回对应元素下标，否则返回-1
int searchSqList(SqList &l, int target)
{
    for (int i = 0; i < l.length; i++)
    {
        if (l.data[i] = target)
        {
            return i;
        }
    }
    return -1;
}

/**
 * 2.2.3.01从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。
 * 空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
 * 思路：遍历顺序表，查找最小元素，并记住位置，完成搜索后用最后一个元素填补原最小值元素的位置
 */
bool delMin(SqList &L, int value)
{
    if (L.length == 0)
        return false;

    value = L.data[0];
    int pos = 0;
    for (int i = 1; i < L.length; i++)
    {
        if (L.data[i] < value)
        {
            value = L.data[i];
            pos = i;
        }
    }
    L.data[pos] = L.data[L.length - 1];
    L.length--;
    return true;
}

/**
 * 2.2.3.02.设计一个高效算法，将顺序表L的所有元素逆置，
 * 要求算法的空间复杂度为O(1).
 *
 * 思路：遍历前半部分顺序表，将顺序表首尾交换位置
 */
void Reverse(SqList &L)
{
    int temp = 0;
    for (int i = 0; i < L.length / 2; i++)
    {
        temp = L.data[i];
        L.data[i] = L.data[L.length - i - 1];
        L.data[L.length - i - 1] = temp;
    }
}

/**
 * 2.2.3.04.从顺序表中删除其值在给定值s和t之间(包含s和t，要求s<t) 的所有元素，
 * 若s或t不合理或顺序表为空，则显示出错信息并退出运行。
 * 思路：从前向后扫描L，用k记录处在[s,t]之间元素个数，
 * 若当前元素属于[s,t]则k++，否则将该元素向前移动k个位置
 */
bool deleteTargetsBetweenSTSqList(SqList &l, int s, int t)
{
    if (l.length > 0 && s < t)
    {
        for (int i = 0, k = 0; i < l.length - 1; i++)
        {

            if (s <= l.data[i] && l.data[i] <= t)
                k++;
            l.data[i - k] = l.data[i];
            l.length -= 1;
        }
        return 1;
    }
    return 0;
}

/**
 * 2.2.3.05.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
 * 思路：双指针:定义i = 1,j = 0.i遍历顺序表，
 *          若当前元素=前一个元素则i++，
 *          若不等于，则j++，将i赋给j
 */
bool deleteRepeatSqList(SqList &l)
{
    if (l.length > 0)
    {
        int i, j;
        for (i = 1, j = 0; i < l.length; i++)
        {

            if (l.data[i] != l.data[j])
                l.data[++j] = l.data[i];
        }
        l.length = j + 1;
        return 1;
    }
    return 0;
}

/**
 * 2.2.3.06.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
 * 从两个顺序表中去最小的存入新的顺序表，最后剩于的全部放入顺序表中
 */
SqList mergeOrderedSqList(SqList A, SqList B)
{
    SqList temp;

    int i = 0, j = 0, k = 0;
    for (; i < A.length && j < B.length;)
    {
        if (A.data[i] < B.data[j])
        {
            temp.data[k++] = A.data[i++];
        }
        else
        {
            temp.data[k++] = B.data[j++];
        }
    }
    while (i < A.length)
    {
        temp.data[k++] = A.data[i++];
    }
    while (j < B.length)
    {
        temp.data[k++] = B.data[j++];
    }
    temp.length = k;
    return temp;
}

/**
 * 王道2.2.3.07已知在一维数组A[m+n]中依次存放两个线性表(a),a2,a3,,am)和(b,bz,b3,.., bn)。编写一
个函数,将数组中两个顺序表的位置互换,即将(b,b2,b3,.,bn)放在(a,a2,a3,,am)的前面
 * 思路：两次reverse 1. ---------->------>  2.<------<---------- 3.------>---------->
 */
void Reverse(SqList *A, int left, int right, int arraySize)
{
    if (left >= right || right >= arraySize)
        return;
    int mid = (left + right) / 2;
    for (int i = 0; i <= mid - left; i++)
    {
        SqList temp = A[left + i];
        A[left + i] = A[right - i];
        A[right - i] = temp;
    }
}
void Exchange(SqList A[], int m, int n, int arraySize)
{
    Reverse(A, 0, m + n - 1, arraySize);
    Reverse(A, 0, n - 1, arraySize);
    Reverse(A, n, m + n - 1, arraySize);
}

/**
 * ***********************************************************************************************************************
 * **************************************************单链表(默认带头结点)***************************************************
 * ***********************************************************************************************************************
 */

// 打印链表
void printLNode(LNode *p)
{
    while (p->next != NULL)
    {
        cout << p->next->data << " ";
        p = p->next;
    }
    cout << endl;
}

void createLinkList(LNode *&l)
{
    LNode *L0 = (LNode *)malloc(sizeof(LNode));
    LNode *L1 = (LNode *)malloc(sizeof(LNode));
    LNode *L2 = (LNode *)malloc(sizeof(LNode));
    LNode *L3 = (LNode *)malloc(sizeof(LNode));
    LNode *L4 = (LNode *)malloc(sizeof(LNode));
    LNode *L5 = (LNode *)malloc(sizeof(LNode));
    L0->data = 1;
    l->next = L0;
    L1->data = 2;
    L0->next = L1;
    L2->data = 3;
    L1->next = L2;
    L3->data = 5;
    L2->next = L3;
    L4->data = 7;
    L3->next = L4;
    L5->data = 9;
    L4->next = L5;
    L5->next = NULL;
}
void createLinkList1(LNode *&l)
{
    LNode *L0 = (LNode *)malloc(sizeof(LNode));
    LNode *L1 = (LNode *)malloc(sizeof(LNode));
    LNode *L2 = (LNode *)malloc(sizeof(LNode));
    LNode *L3 = (LNode *)malloc(sizeof(LNode));
    LNode *L4 = (LNode *)malloc(sizeof(LNode));
    LNode *L5 = (LNode *)malloc(sizeof(LNode));
    L0->data = 1;
    l->next = L0;
    L1->data = 2;
    L0->next = L1;
    L2->data = 4;
    L1->next = L2;
    L3->data = 6;
    L2->next = L3;
    L4->data = 7;
    L3->next = L4;
    L5->data = 8;
    L4->next = L5;
    L5->next = NULL;
}
// 头插法建表：每次从头结点后插入一个结点从控制台输入数据， -1表示结束
void createLinkListByHeadInsert(LNode *L)
{
    int temp; // 接收数据
    scanf("%d", &temp);
    L->next = NULL;
    while (temp != -1)
    {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = temp;
        s->next = L->next;
        L->next = s;
        scanf("%d", &temp);
    }
}
// 尾插法建表：每次从尾结点后插入一个结点从控制台输入数据， -1表示结束
void createLinkListByTailInsert(LNode *L)
{
    int temp; // 接收数据
    scanf("%d", &temp);
    L->next = NULL;
    // LNode *p = L;
    while (temp != -1)
    {
        LNode *q = (LNode *)malloc(sizeof(LNode));
        q->data = temp;
        q->next = NULL;
        L->next = q;
        L = L->next;
        scanf("%d", &temp);
    }
}

// 按值查找对应节点
LNode *searchLNodeByValue(LNode *l, int target)
{
    LNode *p = l->next;
    while (p != NULL && p->data != target)
    {
        p = p->next;
    }
    return p;
}

// 查找第index个结点
LNode *searchLNodeByIndex(LNode *l, int index)
{
    while (l->next != NULL && index > 0)
    {
        l = l->next;
        index--;
    }
    return l;
}

// 插入结点：将结点p,插入到index后
bool insertLNodeByIndex(LNode *l, LNode *node, int index)
{
    // 找到第index个结点
    l = searchLNodeByIndex(l, index);
    if (l != NULL)
    {
        node->next = l->next;
        l->next = node;
        return true;
    }
    return false;
}

// 按位置删除结点(位置从1开始算) 错误原因，关于index下标没有搞清楚
bool deleteLNodeByIndex(LNode *l, int index)
{
    if (l != NULL && index > 0)
    {
        while (l->next != NULL && index > 1)
        {
            l = l->next;
            index--;
        }
        if (l->next != NULL)
        {
            LNode *p = l->next;
            l->next = l->next->next;
            free(p);
            return true;
        }
        return false;
    }
    return false;
}

// 按值删除结点
bool deleteLNodeByValue(LNode *l, int value)
{
    if (l->next == NULL)
        return 0;
    while (l->next != NULL)
    {
        if (l->next->data == value)
        {
            LNode *temp = l->next;
            l->next = l->next->next;
            free(temp);
            continue;
        }
        l = l->next;
    }
    return 0;
}

/**
 *  删除单链表的一个最小节点(假设该节点唯一)
 * 双指针：定义一个minNode，遍历链表，通过打擂台法寻找链表中最小值，
 * 定义一个preMinNode指向当前最小节点的前驱节点
 * 完成遍历后通过preMinNode删除minNode。
 */
bool deleteMinLNode(LNode *l)
{
    if (l->next != NULL)
    {
        int temp = l->next->data;
        LNode *p = l, *preMinNode;
        while (p->next != NULL)
        {
            if (p->next->data < temp)
            {
                temp = p->next->data;
                preMinNode = p;
            }
            p = p->next;
        }
        LNode *q = preMinNode->next;
        preMinNode->next = preMinNode->next->next;
        free(q);
        return true;
    }
    return false;
}

/**
 * leetcode 160 相交链表 王道2.3.7.18
 * 思路：设两个链表LA长度为m，LB长度为n,公共结点长度为c，
 *      则LA独自长度为a = m-c,LB长度为b = n-c
 *      m + b = n + a
 * 如果没有交集
 *      1，如果 m=n，则两个指针会同时到达两个链表的尾节点，然后同时变成空值 null，此时返回 null；
 *      2.如果 m!=n，则由于两个链表没有公共节点，两个指针也不会同时到达两个链表的尾节点，
 * 因此两个指针都会遍历完两个链表，在指针 pA 移动了 m+n 次、指针 pB 移动了 n+m 次之后，两个指针会同时变成空值 null，此时返回 null。
 */
struct LNode *getIntersectionNode(struct LNode *headA, struct LNode *headB)
{
    if (headA == NULL || headB == NULL)
    {
        return NULL;
    }
    struct LNode *pA = headA, *pB = headB;
    while (pA != pB)
    {
        pA = pA == NULL ? headB : pA->next;
        pB = pB == NULL ? headA : pB->next;
    }
    return pA;
}

// 逆序单链表 思路：遍历链表，使用头插法建一个新链表
void reverseLNode(LNode *l)
{
    LNode *p = l->next;
    LNode *q = p->next;
    l->next = NULL;
    while (q != NULL)
    {
        p->next = l->next;
        l->next = p;
        p = q;
        q = q->next;
    }
    p->next = l->next;
    l->next = p;
}

/**
 * A,B元素正好拉链式分布在C中，只要遍历C过程中先尾插一次A，再头插一次B
 */
void splitC(LNode *C, LNode *A, LNode *B)
{
    LNode *p = C, *q = A;
    bool tag = true; // 定义一个标记是否是A元素，插入A后置为false，插入B后置为true
    while (p->next != NULL)
    {
        LNode *temp = (LNode *)malloc(sizeof(LNode));
        temp->next = NULL;
        temp->data = p->next->data;

        if (tag)
        { // 头插法将temp插入A中
            tag = false;
            q->next = temp;
            q = temp;
        }
        else
        { // 尾插法将temp插入B中
            tag = true;
            temp->next = B->next;
            B->next = temp;
        }
        p = p->next;
    }
}

/**
 * 设单链表的表头指针为L，结点结构由data和next两 个区域构成，其中data域为字符型。
 * 试设计算法判断该链 表的全部n个字符是否中心对称。例如xyx,xyyx都是中心 对称 。
 * 思路：定义指针i,定义一个数组作为栈，首先i,向前移动n/2次，移动过程中将元素入栈。
 *      如果n为奇数则将i向前移动两次，否则移动一次。
 *      再次循环，i每向前移动一次，就从栈中弹出一个元素，与当前元素比较，
 *      若有不相同的元素return  false。
 *      执行完毕return true
 * 总结：top++，后需要先--才能再用，
 */
bool isCenterStmmetry(CLNode *l, int n)
{
    if (l != NULL)
    {
        CLNode *temp[MAXSIZE];
        int top = 0;
        int i = 0;
        CLNode *p = l->next;
        while (i < n / 2)
        {
            temp[top++] = p;
            i++;
            p = p->next;
        }
        if (n % 2 != 0)
        {
            p = p->next;
        }
        while (p != NULL)
        {
            if (temp[--top]->data != p->data)
            {
                return false;
            }
            p = p->next;
        }
    }
    return true;
}

/**
 * 链表重排	：有一个长度为n有序的带头结点单链表L={a1,a2...an}，
 * 设计一个空间复杂度O(1)，时间上尽可能高效的算法，重新排列L中的结点，
 * 得到线性表L'={a1，an，a2，a(n-1)，a3，a(n-2)	}，
 * 给出算法设计思想并实现，说明时间复杂度
 * 思路：双指针+链表中部+链表翻转+链表合并
 * 时间复杂度：O(N)，其中 N 是链表中的节点数。
 * 空间复杂度：O(1)。
 */
LNode *middleNode(LNode *head)
{
    LNode *slow = head;
    LNode *fast = head;
    while (fast->next != NULL && fast->next->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
// 逆转不带头结点的链表 思路：每次翻转，将后面的结点指向前一个结点
LNode *reverseList(LNode *head)
{
    LNode *prev = NULL;
    LNode *curr = head;
    while (curr != NULL)
    {
        LNode *nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}
void mergeList(LNode *l1, LNode *l2)
{
    LNode *l1_tmp;
    LNode *l2_tmp;
    while (l1 != NULL && l2 != NULL)
    {
        l1_tmp = l1->next;
        l2_tmp = l2->next;

        l1->next = l2;
        l1 = l1_tmp;

        l2->next = l1;
        l2 = l2_tmp;
    }
}
void realignLinkList(LNode *head)
{
    if (head == NULL)
    {
        return;
    }
    LNode *mid = middleNode(head);
    LNode *l1 = head;
    LNode *l2 = mid->next;
    mid->next = NULL;
    l2 = reverseList(l2);
    mergeList(l1, l2);
}

/**
 * 2.针对双向链表结构，增加一个访问频度域freq，在链表被启用前， 其初值为零。 
 * 给出其存储结构的C语言描述; 
 * typedef struct DFreqLNode{
 *      int data;
 *      int freq;
 *      struct DFreqLNode *pre;
 *      struct DFreqLNode *next;
 * }DFreqLNode;
 * 设头指针为L的带有头结点的非循环双向链表。每当在链表中进行一次Locate(L，x)运算时，
 * 令元素值为x的结点中freq域的值增1，并使此链表中结点按访问频度非增(递减)的顺序排列，
 * 同时最近访问的结点排在频度相同的结点前面，返回找到的结点的地址。
 */
DNode *Locate(DLinkList &L, int x)
{
    DNode *p = L->next,*q; // p为工作指针，q为p的前驱，用于查找插入位置
    while (p && p->data != x)
        p = p->next;
    if (!p)
        return NULL; // 不存在值为x的结点
    else
    {
        p->freq++; // 频域自增
        if (p->prior == L || p->prior->freq > p->freq)
            return p; // p 是链首结点，或者freq值小于前驱
        if (p->next != NULL)
            p->next->prior = p->prior;
        p->prior->next = p->next; // 将p结点从链表上摘下
        q = p->prior;             // 以下查找p结点的插入位置
        while (q != L && q->freq <= p->freq)
            q = q->prior;
        p->next = q->next;
        if (q->next != NULL)
            q->next->prior = p; // 将p结点排在同频率第一个
        p->prior = q;
        q->next = p;
    }
    return p;
}

/**
 * 链表并集 :
 * 求两个递增有序带头结点链表LA和LB的并集，形成的新的链表，假设这两个链表都不含有重复的数字，
 *  求并集指的是LA和LB共有的元素只保留一个
 * 思路：1.首先，我们设定一个哨兵节点 prehead ，这可以在最后让我们比较容易地返回合并后的链表。
 * 2.我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。将符合条件的结点加入preHead
 * 3.初始化preHead，将l1和l2中最小的放入preHead
 * 4.我们重复以下过程，直到 l1 或者 l2 指向了 null ：
 *      4.1若prev->data == l2->data，l2指针往后移一位，并跳过本次循环
 *      4.2若 l1 当前节点的值小于等于 l2 ，把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。
 *          否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位。
 * 5.在循环终止的时候，l1 和 l2 至多有一个是非空的。将非空链表接在合并链表的后面，并返回合并链表即可。
 * 由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。
 */
// LNode *mergeTwoLists(LNode *l1, LNode *l2)
// {
//     LNode *preHead = (LNode *)malloc(sizeof(LNode));
//     LNode *prev = preHead;
//     l1 = l1->next;
//     l2 = l2->next; // 去头
//     // 此时prev处于头结点位置，先将较小的一个结点放入，以用于后面的比较
//     if (l1->data <= l2->data)
//     {
//         prev->next = l1;
//         l1 = l1->next;
//         prev = prev->next;
//     }
//     else
//     {
//         prev->next = l2;
//         l2 = l2->next;
//         prev = prev->next;
//     }

//     while (l1 != NULL && l2 != NULL)
//     {
//         if (prev->data == l2->data)
//         {
//             l2 = l2->next;
//             continue;
//         }
//         else if (l1->data <= l2->data)
//         { // 如果pre是头结点则直接将较小的
//             prev->next = l1;
//             l1 = l1->next;
//         }
//         else if (l1->data > l2->data)
//         {
//             prev->next = l2;
//             l2 = l2->next;
//         }
//         prev = prev->next;
//     }
//     // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
//     prev->next = l1 == NULL ? l2 : l1;
//     return preHead;
// }

/**
 * 王道练习题2.3.7.8 p43
 * 思路：定义双指针p,q，分别遍历A,B，依次比较A,B中的元素，
 *          若不等，值小的向后移动，
 *          若相等，创建一个新的结点尾插法插入ans中，并且两个指针向后移动
 */
LNode *getCommon(LNode *A, LNode *B)
{
    LNode *ansHead = (LNode *)malloc(sizeof(LNode));
    ansHead->next = NULL;
    LNode *p = A, *q = B, *ans = ansHead;
    while (p->next != NULL && q->next != NULL)
    {
        if (p->next->data == q->next->data)
        {
            LNode *temp = (LNode *)malloc(sizeof(LNode));
            temp->data = p->next->data;
            temp->next = ans->next;
            ans->next = temp;
            ans = temp;
            p = p->next;
            q = q->next;
        }
        else if (p->next->data < q->next->data)
        {
            p = p->next;
        }
        else if (p->next->data > q->next->data)
        {
            q = q->next;
        }
    }
    return ansHead;
}

/**
 * 王道练习题2.3.7.9 p43
 * 思路：若共同存在就保留，否则就就删除，
 *      若B先遍历完就把A当前结点的NEXT置为空，
 *      若A先遍历完B就全部置为空
 */
LNode *findUnion(LNode *A, LNode *B)
{
    LNode *p = A, *q = B, *r = A;
    LNode *temp = q->next;
    while (p->next != NULL && q->next != NULL)
    {
        if (p->next->data == q->next->data)
        {
            r->next = p->next;
            p = p->next;
            r = r->next;

            q->next = q->next->next;
            q = q->next;
            free(temp);
        }
        else if (p->next->data < q->next->data)
        {
            temp = p->next;
            p = p->next;
            free(temp);
        }
        else if (p->next->data > q->next->data)
        {
            temp = q->next;
            q = q->next;
            free(temp);
        }
    }
    while (p->next != NULL)
    {
        temp = p->next;
        p = p->next;
        free(temp);
    }
    while (q->next != NULL)
    {
        temp = q->next;
        q = q->next;
        free(temp);
    }
    r->next = NULL;
    free(B);
    return A;
}

/**
 * 王道练习题2.3.7.10 p43
 * 思路：10.双指针：定义两个指针p，q，q作为p的前驱结点，
 * 用p遍历链表，若p对应的data与B的第一个元素相等
 * 就开始判断p及以后的结点和B是否一一对应，若对应返回true，
 * 否则p = q->next->next
 */
int Pattern(LNode *A, LNode *B)
{
    LNode *p = A;   // p为A链表的工作指针，本题假定A和B均无头结点
    LNode *pre = p; // pre记住每趟比较中A链表的开始结点
    LNode *q = B;   // q是B链表的工作指针
    while (p && q)
    {
        if (p->data == q->data)
        { // 结点值相同
            p = p->next;
            q = q->next;
        }
        else
        {
            pre = pre->next;
            p = pre; // A链表新的开始比较结点
            q = B;   // q从B链表第一个结点开始
        }
    }

    if (q == NULL) // B 已经比较结束
        return 1;  // 说明B是A的子序列
    else
        return 0; // B不是A的子序列
}

/**
 * 王道练习题2.3.7.12 p43
 * 思路：先找到两个链表的尾结点，将L1的尾结点指向L2头结点，将L2尾结点指向L1头结点
 */
LNode *linkAB(LNode *A, LNode *B)
{
    LNode *p, *q;
    p = A;
    q = B;
    while (p->next != A)
        p = p->next;

    while (q->next != B)
        q = q->next;
    p->next = B;
    q->next = A;
    return A;
}

/**
 * 王道练习题2.3.7.14 p44
 * 链表右移k
 * 思路：先找到两个链表的尾结点，将L1的尾结点指向L2头结点，将L2尾结点指向L1头结点
 */
LNode *Converse(LNode *L, int k)
{
    int n = 1;
    LNode *p = L;
    while (p->next != NULL)
    {
        p = p->next;
        n++;
    }
    p->next = L;
    for (int i = 1; i <= n - k; i++)
        p = p->next;
    L = p->next;
    p->next = NULL;
    return L;
}

/**
 * 王道练习题2.3.7.15 p44
 * 判断链表中是否有环
 * 定义两个指针fast和slow，遍历链表，
 * 每次slow向前走一步，fast向前走两步，若两个相遇则说明链表中有环，否则没有
 */
LNode *FindLoopStart(LNode *head)
{
    LNode *fast = head, *slow = head; // 设置快慢两个指针
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        // 每次走一步/1每次走两步//相遇
        fast = fast->next->next;
        if (slow == fast)
            break;
    }
    if (fast == NULL || fast->next == NULL)
        return NULL;
    LNode *p1 = head, *p2 = slow;
    while (p1 != p2)
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    // 没有环，返回NULL1/分别指向开始点、相
    return p1;
}

/**
 * 王道2.3.7.16、
 * 设有一个长度n(n为偶数)的不带头结点的单链表，且结点值都大于0，
 * 设计算法求这个单链表的最大孪生和。孪生和定义为一个结点值与其孪生结点值之和，
 * 对于第i个结点(从0开始)，其孪生结点为第n-i-1个结点。
 * 要求:
 *      1)给出算法的基本设计思想。
 *      2)根据设计思想，采用C或 C++语言描述算法，关键之处给出注释。
 *      3)说明你所设计算法的时间复杂度和空间复杂度。
 * 思路：即求链表回文和（第一个和最后一个的和，第二个和倒数第二个的和，...），
 * 定义双指针p,q，p移动一次，q移动两次方式遍历链表，同时使用头插发创建新的链表p，直到p找到链表中部，q找到链表尾部，
 * 然后将q指向新链表表头，p继续向后移动，p,q每次移动一次，并求和，以打擂台方式寻找最大和
 * 时间复杂度：p每次往后移动一次遍历了一次链表，
 *            q先是每次往后移动一次，遍历了n/2的链表，后来每次往后移动一次遍历了半个链表
 *            时间复杂度为O(N)
 * 空间复杂度：未额外使用结点所以空间复杂度O(1)
 */
int pairSum(LNode *L)
{
    if (L == NULL) // 如果链表长度为0，0是最小的偶数
        return -1;

    LNode *p = L, *q = L->next, *temp = NULL, *newHead;
    newHead->next = NULL;

    while (q != NULL && q->next != NULL) // 遍历的同时头插法新建链表
    {
        temp = p;
        temp->next = newHead->next;
        newHead->next = temp;
        p = p->next;
        q = q->next->next;
    }

    q = newHead->next;
    p = p->next; // p需要在走一次才能到链表右半边的开头

    int maxPairSum = 0;
    while (p != NULL)
    {
        int sum = p->data + q->data; // 求孪生和
        if (sum > maxPairSum)        // 通过打擂台法找到孪生和的最大值
        {
            maxPairSum = sum;
        }
        p = p->next;
        q = q->next;
    }

    return maxPairSum;
}

/**
 * 王道2.3.7.17.【2009 统考真题】
 * 已知一个带有表头结点的单链表，结点结构为 data link
 * 假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，
 * 查找链表中倒数第k个位置上的结点(k为正整数)。
 * 若查找成功，算法输出该结点的 data 域的值，并返回 1;否则，只返回 0。
 * 要求:
 *      1)给出算法的基本设计思想。
 *      2)描述算法详细实现步骤
 *      3)写出代码
 *
 * 思路：采用双指针，q指针先向后移动k次，
 *      然后p,q同时向后移动，直到q遍历完链表为止，此时p为倒数第k个元素
 *
 * 算法基本设计思想：
 *      1.若list是空链表，则返回0
 *      2.p,q两个指针指向头指针list的下一个结点
 *      3.q先向后移动k次，期间若出现q为NULL情况，则说明k超出链表长度，返回0
 *      4.然后后p,q同时向后移动，直到q遍历完链表为止
 *      5.输出p的data
 */
int findLastButK(LNode *list, int k)
{
    if (list->next == NULL) // 排除链表为空情况
        return 0;

    LNode *p = list->next, *q = list->next;
    for (int i = 0; i < k; i++)
    {
        if (q != NULL)
            q = q->next;
        else // 链表不够长
            return 0;
    }

    while (q != NULL)
    {
        q = q->next;
        p = p->next;
    }
    cout << p->data << endl;
    return 1;
}

/**
 * 王道2.3.7.18.【2012 统考真题】
 * 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时,可共享相同的后缀存储空间，
 * 例如，loading和being的存储映像如下图所示。
 * 设 strl 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为|data|next
 * 请设计一个时间上尽可能高效的算法，找出由str1和str2 所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置P)
 * 要求:
 *      1)给出算法的基本设计思想。
 *      2)根据设计思想，采用C或 C++语言描述算法，关键之处给出注释。
 *      3)说明你所设计算法的时间复杂度和空间复杂度。
 */
/*求链表长度的函数*/
int listlen(LNode *head)
{
    int len = 0;
    while (head->next != NULL)
    {
        len++;
        head = head->next;
    }
    return len;
}
/*找出共同后缀的起始地址*/
LNode *findCommon(LNode *str1, LNode *str2)
{
    int m, n;
    LNode *p, *q;
    m = listlen(str1); // 求 str1的长度，O(m)
    n = listlen(str2); // 求 str2的长度，0(n)

    for (p = str1; m > n; m--) // 若 m>n，使p指向链表中的第
        p = p->next;
    for (q = str2; m < n; n--)
        q = q->next; // 若 m<n，使q指向链表中的第 n-m+1个结点
    while (p->next != NULL && p->next != q->next)
    { // 查找共同后缀起始点//两个指针同步向后移动
        p = p->next;
        q = q->next;
    }
    return p->next; // 返回共同后缀的起始地址
}

/**
 * 王道2.3.7 19.【2015 统考真题】
 * 用单链表保存m个整数，结点的结构为[data][link]，且|datan(n为正整数)。
 * 现要求设计一个时间复杂度尽可能高效的算法，
 * 对于链表中 data 的绝对值相等的点，仅保留第一次出现的结点
 * 思路：要求时间复杂度尽可能高效，所以使用数组模拟哈希表，存储已经出现过的绝对值
 * 若前面已经出现过了，就把当前结点删除掉
 * 时间复杂度为0(m)，空间复杂度为0(n)。
 */
void func(LNode *h, int n)
{
    LNode *p = h, *r;
    int *q, m;
    q = (int *)malloc(sizeof(int) * (n + 1)); // 申请n+1个位置的辅助空间
    for (int i = 0; i < n + 1; i++)           // 数组元素初值置0
        *(q + i) = 0;
    while (p->next != NULL)
    {
        m = p->next->data > 0 ? p->next->data : -p->next->data;
        if (*(q + m) = -0) // 判断该结点的data是否已出现过
        {                  // 首次出现
            *(q + m) = 1;
            p = p->next; // 保蜜
        }
        else // 重复出现
        {    // 删除
            r = p->next;
            p->next = r->next;
            free(r);
        }
    }
    free(q);
}

/**
 * leetcode 21
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 算法设计：
 * 1.设定一个哨兵节点 prehead ，方便返回合并后的链表。
 * 2.维护一个 prev 指针，调整它的 next 指针。然后，重复以下过程，直到 l1 或者 l2 指向了 null
 *      1.如果 l1 当前节点的值小于等于 l2 ，我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。
 *      2.否则，我们对 l2 做同样的操作。
 *      3. prev 向后移一位。
 * 3.在循环终止的时候， l1 和 l2 至多有一个是非空的。将非空链表接在合并链表的后面，并返回合并链表即可。
 */
LNode *mergeTwoLists(LNode *l1, LNode *l2)
{
    LNode *preHead = NULL;
    LNode *prev = preHead;
    while (l1 != nullptr && l2 != nullptr)
    {
        if (l1->data < l2->data)
        {
            prev->next = l1;
            l1 = l1->next;
        }
        else
        {
            prev->next = l2;
            l2 = l2->next;
        }
        prev = prev->next;
    }
    // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
    prev->next = l1 == nullptr ? l2 : l1;
    return preHead->next;
}

/**
 * leetcode 83 删除重复元素
 * 对链表进行一次遍历，就可以删除重复的元素。从指针 cur 指向链表的头节点，随后开始对链表进行遍历。
 * 如果当前 cur 与 cur.next 对应的元素相同，那么我们就将 cur.next 从链表中移除；
 * 否则说明链表中已经不存在其它与 cur 对应的元素相同的节点，因此可以将 cur 指向 cur.next。
 * 当遍历完整个链表之后，返回链表的头节点即可。
 */

LNode *deleteDuplicates(LNode *head)
{
    if (!head)
        return head;
    LNode *cur = head;
    while (cur->next)
    {
        if (cur->data == cur->next->data)
            cur->next = cur->next->next;
        else
            cur = cur->next;
    }
    return head;
}
/**
 * *********************************************************************************************************************
 * *******************************************************双链表(默认带头结点)********************************************
 * *********************************************************************************************************************
 */

// 打印双链表
void printDLNode(DLNode *head)
{
    while (head->next != NULL)
    {
        cout << head->next->data << " ";
        head = head->next;
    }
    cout << endl;
}

void printDLNodeF(DLNodeF *head)
{
    while (head->next != NULL)
    {
        cout << head->next->data << " ";
        head = head->next;
    }
    cout << endl;
}
// 创建二叉链表
void createDLNode(DLNode *head)
{
    int n; // 接收数据
    cin >> n;
    head->next = NULL; // 初始化
    while (n)
    {
        int temp;
        cin >> temp;
        DLNode *s = (DLNode *)malloc(sizeof(DLNode));
        s->data = temp;
        s->next = NULL;
        head->next = s;
        s->prior = head;
        head = head->next;
        n--;
    }
}

void createDLNodeF(DLNodeF *head)
{
    int n; // 接收数据
    cin >> n;
    head->next = NULL; // 初始化
    while (n)
    {
        int temp;
        cin >> temp;
        DLNodeF *s = (DLNodeF *)malloc(sizeof(DLNodeF));
        s->data = temp;
        s->next = NULL;
        head->next = s;
        s->prior = head;
        head = head->next;
        n--;
    }
}

/**
 * 王道练习题2.3.7.11 p43
 * 思路：双指针：定义两个指针p,q，p从前往后遍历，q从前往后遍历，
 * 同时比较元素是否相等,直到他们指向同一个结点
 */
bool symmetry(DLNode *L)
{
    DLNode *p = L->next, *q = L->prior;
    while (p != q && q->next != p)
    {
        if (p->data == q->data)
        {
            p = p->next;
            q = q->prior;
        }
        else
            return false;
    }
    return true;
}

/**
 * 王道练习题2.3.7.13 p43
 * 思路：遍历链表，若当前结点值为x则将freq++，然后将该结点取出，向前寻找该结点插入位置
 */
DLNodeF *locateX(DLNodeF *L, int x)
{
    DLNodeF *p = L->next, *temp, *q;
    while (p != NULL)
    {
        if (p->data == x)
        {
            p->freq++;
            // 取出结点
            temp = p;
            q = p;
            p->next->prior = p->prior;
            p->prior->next = p->next;
            p = p->next;
            while (true)
            {
                if (q == L)
                {
                    temp->next = q->next;
                    q->next->prior = temp;
                    temp->prior = q;
                    q->next = temp;
                    return temp;
                }
                if (q->freq > temp->freq)
                {
                    temp->next = q->next;
                    q->next->prior = temp;
                    temp->prior = q;
                    q->next = temp;
                    return temp;
                }
                q = q->prior;
            }
        }
        p = p->next;
    }
    return NULL;
}

int main()
{
    /********************************单链表(默认带头结点)********************************/
    // LNode *L = (LNode *)malloc(sizeof(LNode));
    // createLinkList(L);
    // printLNode(L);
    // createLinkListByHeadInsert(L);
    // createLinkListByTailInsert(L);
    // createLinkList(L);
    // printLNode(L);
    //
    // temp = searchLNodeByValue(L,4);
    // temp = searchLNodeByIndex(L, 4);
    //
    // temp = (LNode*)malloc(sizeof(LNode));
    // temp->data = 3;
    // insertLNodeByIndex(L, temp, 2);
    // printLNode(L);
    //
    // int i = deleteLNodeByIndex(L, 3);
    // cout<< i<<endl;
    // printLNode(L);
    //
    // deleteLNodeByValue(L, 3);
    // printLNode(L);

    // createLinkList(L);
    // printLNode(L);
    // deleteMinLNode(L);
    // printLNode(L);

    // L0->data = 1;L1->data = 2;L2->data = 3;L3->data = 4;L4->data = 5;
    // L->next = L0;L0->next = L1;L1->next = L2;L2->next = L3;L3->next = L4;L4->next = NULL;
    // printLNode(L);
    // reverseLNode(L);
    // printLNode(L);

    // realignLinkList(L);

    // LNode *L2 = (LNode *)malloc(sizeof(LNode));
    // createLinkList1(L2);
    // printLNode(L2);
    // temp = mergeTwoLists(L, L2);
    // printLNode(temp);

    // LNode *A = (LNode *)malloc(sizeof(LNode));
    // A->next = NULL;
    // LNode *B = (LNode *)malloc(sizeof(LNode));
    // B->next = NULL;
    // splitC(L, A, B);
    // printLNode(A);
    // printLNode(B);

    /**
     *
     * ****************************************double单链表(默认带头结点)*****************************************
     *
     */

    // DLNode *head = (DLNode*)malloc(sizeof(DLNode));
    // DLNode *temp = NULL;
    // createDLNode(head);
    // printDLNode(head);

    DLNodeF *head = (DLNodeF *)malloc(sizeof(DLNodeF));
    createDLNodeF(head);
    printDLNodeF(head);

    // int a = deleteLNodeByIndex(L,3);
    // cout<< a <<endl;
    // printLNode(L);

    // temp = searchLNodeByValue(L,5);
    // cout<<temp->data<<endl;

    // isCenterStmmetry
    // CLNode *l = (CLNode *)malloc(sizeof(CLNode));
    // CLNode *l0 = (CLNode *)malloc(sizeof(CLNode));
    // CLNode *l1 = (CLNode *)malloc(sizeof(CLNode));
    // CLNode *l2 = (CLNode *)malloc(sizeof(CLNode));
    // CLNode *l3 = (CLNode *)malloc(sizeof(CLNode));
    // CLNode *l4 = (CLNode *)malloc(sizeof(CLNode));
    // l->next = l0;
    // l0->data = 'A';l0->next = l1;
    // l1->data = 'B';l1->next = l4;
    // l4->data = 'C';l4->next = l2;
    // l2->data = 'B';l2->next = l3;
    // l3->data = 'A';l3->next = NULL;
    // int a = isCenterStmmetry(l,5);
    // cout<< a;

    locateX(head, 2);
    printDLNodeF(head);

    // system("pause");
    return 0;
}